
// swap 2 elements in array 'a'
void Swap(int a[], int p1, int p2)
{
	int x = a[p1];
	a[p1] = a[p2];
	a[p2] = x;
}

// UpHeap
// the element at 'pos' is recently updated:
// check if that element is valid,
// if it's not valid, move it up
int UpHeap(int a[], int pos)
{
	// this is root element, cannot up any more
	if (0 == pos)
		return 0;

	// find parent element
	int parent = (pos-1) / 2;

	// if the updated element is not valid, move it up
	if (a[parent] < a[pos])
	{
		Swap(a, parent, pos);
		return parent; // continue UpHeap
	}
	else // the element is valid, no need to move up
		return 0;
}

// DownHeap
// the element at 'pos' is recently updated:
// check if that element is valid,
// if it's not valid, move it up
int DownHeap(int a[], int n, int pos)
{
	// check if the element has no children
	if (n <= pos * 2 + 1)
		return 0;

	// find position of maximum child
	// second child exists
	// first child is less than second child
	int maxChild = pos * 2 + 1;			// maxChild is first child
	if (maxChild + 1 < n &&	a[maxChild] < a[maxChild + 1])
		maxChild = maxChild + 1;		// change maxChild to second child

	// check if the element needs to be moved down
	if (a[pos] < a[maxChild])
	{
		Swap(a, pos, maxChild);
		return maxChild; // continue DownHeap
	}
	
	// stop moving
	return 0;
}

int main_heap_sort()
{
	int n=6;
	int a[]={12, 2, 8, 5, 1, 6};

	// step1: create heap
	for (int i=1; i<n; i++)
	{
		int ret = UpHeap(a, i);
		while (0 != ret)
			ret = UpHeap(a, ret);
	}

	// step2: pickup top of the heap, and correct the new heap
	for (int i=1; i<n; i++)
	{
		Swap(a, 0, n-i);
		int ret = DownHeap(a, n-i, 0);
		while (0 != ret)
			ret = DownHeap(a, n-i, ret);
	}

	return 0;
}
